題目

https://leetcode.com/problems/palindrome-linked-list/

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space?

解答

C#

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    ListNode realHead;
    bool isCrossed = false;
    public bool IsPalindrome(ListNode head)
    {
        if (head == null)
            return true;

        if (realHead == null)
            realHead = head;

        bool result = true;

        if (head.next != null)
            result = result & IsPalindrome(head.next);

        if (isCrossed)
            return result;
        
        if (head == realHead || realHead.next == head)
        isCrossed = true;

        result = result & (head.val == realHead.val);
        realHead = realHead.next;

        return result;
    }
}

結果

Runtime: 92 ms, faster than 99.6% of C# online submissions.

Memory Usage: 36.1 MB, less than 10.00% of C# online submissions.

Time Complexity: O(n)

Space Complextiy: O(n)

為什麼我要這樣做？

LinkedList 小回顧 ↓
[Day 14] 演算法刷題 LeetCode 21. Merge Two Sorted Lists (Easy)
[Day 15] 演算法刷題 LeetCode 141. Linked List Cycle (Easy)
[Day 16] 演算法刷題 LeetCode 142. Linked List Cycle II (Medium)
[Day 17] 演算法刷題 2. Add Two Numbers (Medium)

這題也使用遞迴 Recursion 的概念去實作

這次要宣告兩個變數在 method 外面等待呼叫

1. ListNode realHead;
   • 用來從 head 往後比對的起始點
2. bool isCrossed = false;
   • 用來判斷當比對的兩個指標交叉後，可以忽略後面的判斷，直接回傳結果，至於這是什麼意思，我晚點在效能調校時來解釋
3. 判斷 realHead 為 null，則指向 head
4. 宣告 bool result 為true
5. 如果 head.next 不為 null 時
   • result = result & IsPalindrome(head.next);
   • 直到 IsPalindrome(head.next) 判斷到 head.next 為 null 時開始回傳
     • 此時兩個指標 realHead 會 從頭往後 開始比較；head 會 從尾往前 開始比較
     • 只要一個遞迴裡 realHead != head，result & IsPalindrome(head.next) 永遠為 false;

可以參考上圖，每個框都是一個遞迴

示意圖

如果看文字敘述不是很明確的話，可以看下面的示意圖。

以 l1: 1->2->1 為例

程式裡就會照這樣的順序去做比對

效能調校

其實當兩個指標 head 及 realHead 交叉後，後面的比較就是重複了

以上圖為例，第三次的比對其實跟第一次的比對是一樣的

所以我在 method 外面宣告 bool isCrossed = false，用來判斷兩個指標是否已經交叉

if (head == realHead || realHead.next == head)` 
        isCrossed = true;

若已經交叉，就不需要再做後面重複的比對了。

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉